package leetcode.editor.day;

// 793. 阶乘函数后 K 个零
// https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/
class PreimageSizeOfFactorialZeroesFunction {
    public static void main(String[] args) {
        Solution solution = new PreimageSizeOfFactorialZeroesFunction().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/solution/jie-cheng-han-shu-hou-k-ge-ling-by-leetc-n6vj/
        public int preimageSizeFZF(int k) {
            return (int) (helper(k + 1) - helper(k));
        }

        public long helper(int k) {
            long l = 0, r = 5L * k;
            while (l < r) {
                long m = l + (r - l) / 2;
                if (zeta(m) < k) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }

            return r;
        }

        // 172，求阶层尾随0的个数
        public int zeta(long n) {
            int ans = 0;
            while (n != 0) {
                n /= 5;
                ans += n;
            }
            return ans;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
